#pragma once

#include<iostream>
#include<assert.h>
#include<mutex>
#include<algorithm>
#include<unordered_map>

#ifdef _WIN32
#include <windows.h>
#else
// Linux
#include <unistd.h>
#endif // _WIN32

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELIST = 208;
static const size_t NPAGES = 129;
static const size_t PAGE_SHIFT = 13;  // 一页 2 ^ 13 k


// FreeList
// sizeClass
// Span

// 定长池的设计实现


class AllocHelper
{
protected:

	// 申请内存
	inline static void* SystemAlloc(size_t kpage)
	{
#ifdef _WIN32

		// 使用系统调用 ， 脱离 malloc 
		void* ptr = VirtualAlloc(0, kpage * (1 << 13), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);//8 K

#else
		// linux下brk mmap等
		void* ptr = sbrk(kpage * (1 << 13)  );
#endif
		if (ptr == nullptr)
		{
			throw std::bad_alloc();
		}
		return ptr;
	}

	// 释放内存
	inline static void SystemFree(void* ptr)
	{
#ifdef _WIN32
		VirtualFree(ptr, 0, MEM_RELEASE);
#else
		// sbrk unmmap等
#endif
	}
};

class PtrHelper
{
protected:
	static void*& NextObj(void* obj)   // 这里必须用 引用
	{
		return *(void**)obj;    // 取出前四个 字节
	}
};


template<typename T>
class ObjectPool:protected AllocHelper,protected PtrHelper
{
	//void* _memory;   // 为什么不用 void*  ,void* 不能解引用，不能++ ,指针得 解引用，++，才有意义
	char* _memory = nullptr;  // 使用 char* 而非 void* , char* 好用，方便从大块内存切出来一部分
	void* _freeList = nullptr;  // 指向归还回来的空闲区块
	size_t _remainBytes = 0;   // 大内存块在切分中剩余的字节数
	size_t _projectedAllocation = 0;
	size_t _objSize;

	/*size_t num = 0;
	size_t numsss = 0;
	size_t alloc = 0;*/

public:
	ObjectPool(size_t projectedAllocation = 128 * 1024):_projectedAllocation(projectedAllocation)
	{
		// 这一步防止归还的内存连指针都无法存下
		_objSize = sizeof T < sizeof(void*) ? sizeof(void*) : sizeof T;
	}


	T* New()
	{
		T* obj = nullptr;  //待分配区域的首地址
		//void* next = nullptr;
		if (_freeList != nullptr)
		{
			// 有空闲区块
			//next = NextObj(_freeList);   // next 指向下一个空闲区间
			// 这里  *(void**) 可以解决 32位机器和 64 位机器下，指针占用4字节和8字节不同的问题
			// 强转成 void** 二级指针，再解引用成一级指针(void*)
			// 在32位下，指针位 4位，自动分配前4字节 
			// 在64位下，指针位 8位，自动分配前8字节 
			obj = (T*)_freeList;
			_freeList = NextObj(_freeList);;

		}
		else
		{
			// 没有空闲区块
			if (_remainBytes < sizeof T)
			{
				// 但剩余的内存不够一个对象的大小时，则重新开辟更大的空间
				_remainBytes = _projectedAllocation;  // 128 kb
				//_memory = (char*)malloc(_remainBytes);
				size_t page = _remainBytes >> 13;   // 除以 8k , 得到页号
				_memory = (char*)SystemAlloc(page == 0 ? 1 : page);  // 不满一页，则按一页分配
				if (_memory == nullptr)
				{
					throw std::bad_alloc();  // 分配失败
				}
			}

			obj = (T*)_memory;

			//// 这一步防止归还的内存连指针都无法存下
			//_objSize = sizeof T < sizeof(void*) ? sizeof(void*) : sizeof T;

			_memory += _objSize;  // memory 指向下一个未分配的内存块
			_remainBytes -= _objSize;

		}

		// 定位 new，将分配的内存传递给new，new再去调用其构造函数
		new(obj)T;
		return obj;
	}


	void Delete(T* obj)
	{
		NextObj(obj) = _freeList;   // 头插,将新释放的元素的内存前 4个字节的内容修改为指向下一个空闲空间的地址
		_freeList = obj;
	}
};



class FreeList:public PtrHelper
{
	void* _freeList = nullptr;
	
	// 1. 分配内存时，选择合适的内存大小使用， 可以调节最大阈值
	// 2. 回收内存时，比较 _freeList 后的内存数量是否大于 _maxsize , 如果大于，那么回收内存
	size_t _maxsize = 1;  //  centerCache 最多一次分配给 threadCache 的最大阈值
	size_t _size = 0;

private:
	
public:
	void Push(void* obj)
	{
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;
		_size++;
	}

	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}

	// 需要将指针的头尾传递除去
	void PopRange(void*& start, void*& end,size_t n)
	{
		assert(n >= _size);
		
		// 删除
		end = start = _freeList;
		for (size_t i = 1; i < n; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;

		_size -= n;
		/*NextObj(end) = _freeList;
		_freeList = start;
		_size += n;*/
	}

	void* Pop()
	{
		void* obj = _freeList;
		//_freeList = *(void**)_freeList;
		_freeList = NextObj(_freeList);
		_size--;
		return obj;
	}

	bool empty()
	{
		return _freeList == nullptr;
	}

	// 用于外侧调节
	size_t& MaxSize()
	{
		return _maxsize;
	}

	size_t Size()
	{
		return _size;
	}
};


class SizeClass
{
private:

	// 控制在 10% 的内存碎片浪费   
	// 比如：申请129， 系统开 144    浪费 15 ； 15/144 = 10.46
	// 比如：申请1025， 系统开 1152    浪费 127 ； 127/1152 = 11.02
	// ...
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)  // RoundUp 的子函数
	{
		// size 申请的内存大小    alignnum 是当前对齐数 8 16 24 .....

		// [1~8]  -> 8
		// [9~16]  -> 16

		//return (  (bytes - 1)/alignNum    + 1) * alignNum;

		return ((bytes + alignNum - 1) & ~(alignNum - 1));  // 位运算
	}

	static inline size_t _Index(size_t bytes, size_t align_shift)  //  2^(align_shift) 个内存 
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;

		// align_shift	     (1 << align_shift)     (1 << align_shift) - 1)
		// align_shift = 3			 8						7
		// align_shift = 4			 16						15
		// ... 

		// bytes 如果是 [1~8]  , 8byte对齐  (bytes + (1 << align_shift) - 1) 就是 [8~15]
		// 对于  [8~15]  除以 8 btye 再 -1 ， 就是最后哈希桶中对应下标的位置 
	}
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐	    freelist[0,16)
	// [128+1,1024]				16byte对齐	    freelist[16,72)
	// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)

	
	// 计算申请的内存，内存对齐后实际应分配的大小
	static inline size_t RoundUp(size_t bytes)    // 单次分配内存最大为 256k
	{
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if(bytes <1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes < 8 * 1024)  // 8k
		{
			return _RoundUp(bytes, 128);
		}
		else if (bytes <64*1024)  // 64 k
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes < 256 * 1024)   // 256k
		{
			return _RoundUp(bytes, 8*1024);
		}
		else
		{
			// 单次最多申请内存大小超过 256 k       // 对齐方式为 1<<PAGE_SHIFT , 后续可以更改此上限 
			return  _RoundUp(bytes, 1 << PAGE_SHIFT);
		}
	}

	// 计算映射到哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{

		assert(bytes < MAX_BYTES);   // 不能超过最大内存

		// 每个区间有多少个链
		// 0~128 有16个 8byte
		// 129~1024 有56个 16byte
		// ...

		static int group_array[4] = { 16, 56, 56, 56 };

		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];;
		}
		else
		{
			assert(false);
		}
		return -1;
	}


	// thread cache  一次从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;

		// 如果小于 2个，则至少分配两个
		if (num < 2)
		{
			num = 2;
		}

		// 当单个内存块较小时，个数会较多，
		// 但最多一次配分 512
		if (num > 512)
		{
			num = 512;
		}
		return num;
	}

	// 计算一次向系统获取几个页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		// 计算一次分配的最大上限数量
		size_t num = NumMoveSize(size);  
		// 得出最大内存
		size_t npage = num * size;

		// 最大内存 / 8k ，得出分配几页
		npage >>= PAGE_SHIFT;

		// 如果为 0，则至少分配1页
		if (npage == 0)
		{
			npage = 1;
		}
		return npage;
	}

};


// 管理多个连续页的 大块内存跨度结构
class Span
{
public:
	PAGE_ID _pageId = 0;   // 大块内存起始页的编号
	size_t _n = 0;   // 页的数量

	// 双向列表结构
	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _useCount = 0;  // 切好的小内存块，被分配给 thread cache 的计数
	void* _freeList = nullptr;

	bool _isUsed = false;
	size_t _objSize = 0;   // 记录当前这个Span 内存的内存块切分的大小
};

class SpanList
{
	Span* _head;  // Span 的头指针节点
public:
	std::mutex  _mutex;
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	void PushFront(Span* newspan)
	{
		// 头插
		Insert(Begin(), newspan);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	void Insert(Span*pos,Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		//  pos->prev  newSpan pos
		pos->_prev->_next = newSpan;
		newSpan->_prev = pos->_prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span*pos)
	{
		assert(pos);
		assert(pos!=_head);

		pos->_prev->_next = pos->_next;
		pos->_next->_prev = pos->_prev;
	}

	Span* End()
	{
		return _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}
};
